package com.wyw.leetcode.learning.simple;

import java.util.Arrays;

/**
 * leetcode topic 1005
 *  K 次取反后最大化的数组和
 *
 * @Author Mr Wu （yewen.wu.china@gmail.com）
 * @Date 2022/7/6 10:16
 */
public class Topic1005 {
    public static void main(String[] args) {
//        int[] nums = new int[] {4,2,3};
//        System.out.println(largestSumAfterKNegations(nums, 1));

//        int[] nums = new int[] {3,-1,0,2};
//        System.out.println(largestSumAfterKNegations(nums, 3));

        int[] nums = new int[] {2,-3,-1,5,-4};
        System.out.println(largestSumAfterKNegations1(nums, 2));
    }

    /**
     * 暴力破解
     */
    public static int largestSumAfterKNegations(int[] nums, int k) {
        int length = nums.length;

        if(k <= 0) {
            int sum = 0;
            for(int i=0; i<length; i++) {
                sum+=nums[i];
            }
            return sum;
        }

        int min = nums[0];
        int index = 0;
        for(int i = 1; i<length; i++) {
            if(nums[i] < min) {
                min = nums[i];
                index = i;
            }
        }
        nums[index] = 0 - min;
        return largestSumAfterKNegations(nums, --k);
    }

    public static int largestSumAfterKNegations1(int[] nums, int k) {
        int length = nums.length;
        Arrays.sort(nums);
        if(k<=0) {
            int sum = 0;
            for(int i=0; i<length; i++) {
                sum+=nums[i];
            }
            return sum;
        }
        nums[0] = -nums[0];
        return largestSumAfterKNegations(nums, --k);

    }
}
